Tree (graph theory)

Trees
A labeled tree with 6 vertices and 5 edges
Vertices	v
Edges	v - 1
Chromatic number	2

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. A forest is a disjoint union of trees.

The various kinds of trees used as data structures in computer science are not really trees in this sense, but rather, types of ordered directed trees; see below.

1 Definitions
2 Example
3 Facts
4 Enumeration
5 Types of trees
6 See also
7 References

Definitions

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:

G is connected and has no cycles.
G has no cycles, and a simple cycle is formed if any edge is added to G.
G is connected, and it is not connected anymore if any edge is removed from G.
G is connected and the 3-vertex complete graph $K_3$ is not a minor of G.
Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

G is connected and has n − 1 edges.
G has no simple cycles and has n − 1 edges.

An irreducible (or series-reduced) tree is a tree in which there is no vertex of degree 2.

A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected cycle-free graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), all are examples of forests.

The term hedge sometimes refers to an ordered sequence of trees.

A polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either.

A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. The tree-order is the partial ordering on the vertices of a tree with u ≤ v if and only if the unique path from the root to v passes through u. A rooted tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order whenever those ends are vertices of the tree (Diestel 2005, p. 15). Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. In a context where trees are supposed to have a root, a tree without any designated root is called a free tree.

In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex v is a vertex of which v is the parent. A leaf is a vertex without children.

A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices are typically given the labels 1, 2, …, n. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).

An ordered tree is a rooted tree for which an ordering is specified for the children of each vertex.

An n-ary tree is a rooted tree for which each vertex which is not a leaf has at most n children. 2-ary trees are sometimes called binary trees, while 3-ary trees are sometimes called ternary trees.

A terminal vertex of a tree is a vertex of degree 1. In a rooted tree, the leaves are all terminal vertices; additionally, the root, if not a leaf itself, is a terminal vertex if it has precisely one child.

Example

The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2-4-5-6.

Facts

Every tree is a bipartite graph and a median graph. Every tree with only countably many vertices is a planar graph.

Every connected graph G admits a spanning tree, which is a tree that contains every vertex of G and whose edges are edges of G.

Every connected graph with only countably many vertices admits a normal spanning tree (Diestel 2005, Prop. 8.2.4).

There exist connected graphs with uncountably many vertices which do not admit a normal spanning tree (Diestel 2005, Prop. 8.5.2).

Every finite tree with n vertices, with n > 1, has at least two terminal vertices. This minimal number of terminal vertices is characteristic of path graphs; the maximal number, n − 1, is attained by star graphs.

For any three vertices in a tree, the three paths between them have at least one vertex in common.

Enumeration

Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula. It can be proven by first showing that the number of trees with n vertices of degree d₁,d₂,...,d_n is the multinomial coefficient

${n-2 \choose d_1-1, d_2-1, \ldots, d_n-1}.$

An alternative proof uses Prüfer sequences. This is the special case for complete graphs of a more general problem, counting the number of spanning trees in an undirected graph, which can be achieved by computing a determinant according to the matrix tree theorem. The similar problem of counting all the subtrees regardless of size has been shown to be #P-complete in the general case (Jerrum (1994)).

Counting the number of unlabeled free trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. Otter (1948) proved that

${t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,}$

with C = 0.534949606… and α = 2.99557658565… (Here, $f \sim g$ means that $\lim_{n \to \infty} f/g = 1$ , where $f=t(n)$ and $g=C \alpha^n n^{-5/2}$ ). Similarly, he showed that for the number $r(n)$ of unlabeled rooted trees with n vertices holds

$r(n) \sim D\alpha^n n^{-5/2} \quad\text{as } n\to\infty,$

with D = 0.43992401257… and α the same as above (cf. Knuth (1997), Chap. 2.3.4.4 and Flajolet & Sedgewick (2009), Chap. VII.5).

Types of trees

A star is a tree in which there is only one internal node and n − 1 leaves; that is, a star is a tree with as many leaves as possible. A tree with two leaves, the fewest possible, is a path graph. If all nodes in a tree are within distance one of a central path, then the tree is a caterpillar tree. If all nodes are within distance two of a central path, then the tree is a lobster.

References

Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ .
Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, ISBN 9780521898065
Donald E. Knuth. The Art of Computer Programming Volume 1: Fundamental Algorithms. Addison-Wesley Professional; 3rd edition (November 14, 1997).
Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters 51 (3): 111–116, doi:10.1016/0020-0190(94)00085-9, ISSN 0020-0190 .
Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series 49 (3): 583–599, doi:10.2307/1969046, http://jstor.org/stable/1969046 .